package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import helpclass.Point;

/**
 *@author 周杨
 *ShortestPathToGetAllKeys_864 迷宫问题 拿到钥匙 去打开门
 *describe:用广度优先搜索 并且给地图编码 AC 14%
 *2018年11月6日 上午11:46:01
 */
public class ShortestPathToGetAllKeys_864 {
	
	int INF = Integer.MAX_VALUE;
    String[] grid;
    int R, C;
    Map<Character, Point> location;
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};

    public int shortestPathAllKeys(String[] grid) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length();

        //location['a'] = the coordinates of 'a' on the grid, etc.
        location = new HashMap();
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c) {
                char v = grid[r].charAt(c);
                if (v != '.' && v != '#')
                    location.put(v, new Point(r, c));
            }

        int ans = INF;
        int num_keys = location.size() / 2;
        String[] alphabet = new String[num_keys];
        for (int i = 0; i < num_keys; ++i)
            alphabet[i] = Character.toString((char)('a' + i));
        //alphabet = ["a", "b", "c"], if there were 3 keys

        search: for (String cand: permutations(alphabet, 0, num_keys)) {
            //bns : the built candidate answer, consisting of the sum
            //of distances of the segments from '@' to cand[0] to cand[1] etc.
            int bns = 0;
            for (int i = 0; i < num_keys; ++i) {
                char source = i > 0 ? cand.charAt(i-1) : '@';
                char target = cand.charAt(i);

                //keymask : an integer with the 0-th bit set if we picked up
                // key 'a', the 1-th bit set if we picked up key 'b', etc.
                int keymask = 0;
                for (int j = 0; j < i; ++j)
                    keymask |= 1 << (cand.charAt(j) - 'a');
                int d = bfs(source, target, keymask);
                if (d == INF) continue search;
                bns += d;
                if (bns >= ans) continue search;
            }
            ans = bns;
        }

        return ans < INF ? ans : -1;
    }

    public int bfs(char source, char target, int keymask) {
        int sr = location.get(source).x;
        int sc = location.get(source).y;
        int tr = location.get(target).x;
        int tc = location.get(target).y;
        boolean[][] seen = new boolean[R][C];
        seen[sr][sc] = true;
        int curDepth = 0;
        Queue<Point> queue = new LinkedList();
        queue.offer(new Point(sr, sc));
        queue.offer(null);

        while (!queue.isEmpty()) {
            Point p = queue.poll();
            if (p == null) {
                curDepth++;
                if (!queue.isEmpty())
                    queue.offer(null);
                continue;
            }
            int r = p.x, c = p.y;
            if (r == tr && c == tc) return curDepth;
            for (int i = 0; i < 4; ++i) {
                int cr = r + dr[i];
                int cc = c + dc[i];
                if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
                    char cur = grid[cr].charAt(cc);
                    if (cur != '#') {
                        if (Character.isUpperCase(cur) && (((1 << (cur - 'A')) & keymask) <= 0))
                            continue; // at lock and don't have key

                        queue.offer(new Point(cr, cc));
                        seen[cr][cc] = true;
                    }
                }
            }
        }

        return INF;
    }

    public List<String> permutations(String[] alphabet, int used, int size) {
        List<String> ans = new ArrayList();
        if (size == 0) {
            ans.add(new String(""));
            return ans;
        }

        for (int b = 0; b < alphabet.length; ++b)
            if (((used >> b) & 1) == 0)
                for (String rest: permutations(alphabet, used | (1 << b), size - 1))
                    ans.add(alphabet[b] + rest);
        return ans;
    }
	
	/**
	 * describe:广度优先遍历 对钥匙和坐标编码 不知道哪里错了 最后一个用例出错 
	 * 2018年11月6日 上午11:35:33
	 */
	public int shortestPathAllKeys1(String[] grid) {
		char[][] map=new char[grid.length][grid[0].length()];
		int keyNum=0;
		int startX=0,startY=0;
        for(int i=0;i<grid.length;++i) {
        	char []chars=grid[i].toCharArray();
        	for(int j=0;j<chars.length;++j) {
        		map[i][j]=chars[j];
        		if(chars[j]<='z'&&chars[j]>='a') ++keyNum;
        		if(chars[j]=='@') {
        			startX=i;
        			startY=j;
        		}
        	}
        }
        if(keyNum==0)
        	return 0;
        Set<String>	visited=new HashSet<String>();
        Queue<int[]> queue=new LinkedList<int []>();
        int res=0;
        int []start=new int[] {startX,startY,0,0};
        visited.add(help(start));
        queue.offer(start);
        
        while(!queue.isEmpty()) {
        	int size=queue.size();
        	++res;
        	while(size>0) {
        		--size;
        		int []now=queue.poll();
        		int x=now[0],y=now[1],status=now[2],keys=now[3];
        		//top
        		if(x>0&&map[x-1][y]!='#') {
        			if(map[x-1][y]<='z'&&map[x-1][y]>='a') {//即将获得新的钥匙
        				int key=1<<(map[x-1][y]-'a');
        				if((status&key)==0) {//没有这把钥匙 与运算 都为1才为1
        					if(keys+1==keyNum) {
        						return res;
        					}
        					status+=key;
        					int []next=new int[] {x-1,y,status,keys+1};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else if(map[x-1][y]<='Z'&&map[x-1][y]>='A') {
        				int key=1<<(map[x-1][y]-'A');
        				if((status&key)!=0) {//有这把钥匙
        					int []next=new int[] {x-1,y,status,keys};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else {
        				int []next=new int[] {x-1,y,status,keys};
    					String s=help(next);
    					if(!visited.contains(s)) {
    						visited.add(s);
    						queue.offer(next);
    					}
        			}
        		}
        		//down
        		if(x!=map.length-1&&map[x+1][y]!='#') {
        			if(map[x+1][y]<='z'&&map[x+1][y]>='a') {//即将获得新的钥匙
        				int key=1<<(map[x+1][y]-'a');
        				if((status&key)==0) {//没有这把钥匙
        					if(keys+1==keyNum) {
        						return res;
        					}
        					status+=key;
        					int []next=new int[] {x+1,y,status,keys+1};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else if(map[x+1][y]<='Z'&&map[x+1][y]>='A') {
        				int key=1<<(map[x+1][y]-'A');
        				if((status&key)!=0) {//有这把钥匙
        					int []next=new int[] {x+1,y,status,keys};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else {
        				int []next=new int[] {x+1,y,status,keys};
    					String s=help(next);
    					if(!visited.contains(s)) {
    						visited.add(s);
    						queue.offer(next);
    					}
        			}
        		}
        		
        		//left
        		if(y!=0&&map[x][y-1]!='#') {
        			if(map[x][y-1]<='z'&&map[x][y-1]>='a') {//即将获得新的钥匙
        				int key=1<<(map[x][y-1]-'a');
        				if((status&key)==0) {//没有这把钥匙
        					if(keys+1==keyNum) {
        						return res;
        					}
        					status+=key;
        					int []next=new int[] {x,y-1,status,keys+1};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else if(map[x][y-1]<='Z'&&map[x][y-1]>='A') {
        				int key=1<<(map[x][y-1]-'A');
        				if((status&key)!=0) {//有这把钥匙
        					int []next=new int[] {x,y-1,status,keys};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else {
        				int []next=new int[] {x,y-1,status,keys};
    					String s=help(next);
    					if(!visited.contains(s)) {
    						visited.add(s);
    						queue.offer(next);
    					}
        			}
        		}
        		
        		//right
        		if(y!=map[0].length-1&&map[x][y+1]!='#') {
        			if(map[x][y+1]<='z'&&map[x][y+1]>='a') {//即将获得新的钥匙
        				int key=1<<(map[x][y+1]-'a');
        				if((status&key)==0) {//没有这把钥匙
        					if(keys+1==keyNum) {
        						return res;
        					}
        					status+=key;
        					int []next=new int[] {x,y+1,status,keys+1};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else if(map[x][y+1]<='Z'&&map[x][y+1]>='A') {
        				int key=1<<(map[x][y+1]-'A');
        				if((status&key)!=0) {//有这把钥匙
        					int []next=new int[] {x,y+1,status,keys};
        					String s=help(next);
        					if(!visited.contains(s)) {
        						visited.add(s);
        						queue.offer(next);
        					}
        				}
        			}
        			else {
        				int []next=new int[] {x,y+1,status,keys};
    					String s=help(next);
    					if(!visited.contains(s)) {
    						visited.add(s);
    						queue.offer(next);
    					}
        			}
        		}
        	}
        }
        return -1;
    }
	
	private String help(int[] stat) {
		StringBuilder sb=new StringBuilder();
		for(int i:stat)
			sb.append(i).append('_');
		return sb.toString();
	}
}
